;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Copyright 2021 fanguangping
; 
; Licensed under the Apache License, Version 2.0 (the "License");
; you may not use this file except in compliance with the License.
; You may obtain a copy of the License at
; 
;     http://www.apache.org/licenses/LICENSE-2.0
; 
; Unless required by applicable law or agreed to in writing, software
; distributed under the License is distributed on an "AS IS" BASIS,
; WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
; See the License for the specific language governing permissions and
; limitations under the License.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

#lang racket

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Trie class
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(require "../common/constants.scm")
(require "../common/messages.scm")
(require "../common/utils.scm")
(require "Object.scm")

(provide (all-defined-out))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Make TrieNode class
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (MAKE-TrieNode self key value suffix next)
  (lambda (message)
    (cond
      ((= message +G-TrieNode-key+)
       (lambda () key))
      ((= message +G-TrieNode-value+)
       (lambda () value))
      ((= message +G-TrieNode-suffix+)
       (lambda () suffix))
      ((= message +G-TrieNode-next+)
       (lambda () next))

      ((= message +S-TrieNode-key+)
       (lambda (NEW-key) (set! key NEW-key)))
      ((= message +S-TrieNode-value+)
       (lambda (NEW-value) (set! value NEW-value)))
      ((= message +S-TrieNode-suffix+)
       (lambda (NEW-suffix) (set! value NEW-suffix)))
      ((= message +S-TrieNode-next+)
       (lambda (NEW-next) (set! next NEW-next)))

      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; TODO: equals
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Object-equals+)
       (lambda (other)
         '()))

      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; TODO: hash code
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Object-hash-code+)
       (lambda ()
         '()))
      
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; TODO: to string
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Object-to-string+)
       (lambda ()
         '()))
      
      (else +nil+))))

(define (CREATE-TrieNode key value suffix next)
  (create-instance MAKE-TrieNode key value suffix next))

(define (trie-node-key node)
  (ask node +G-TrieNode-key+))
(define (trie-node-value node)
  (ask node +G-TrieNode-value+))
(define (trie-node-suffix node)
  (ask node +G-TrieNode-suffix+))
(define (trie-node-next node)
  (ask node +G-TrieNode-next+))

(define (trie-node-key! node key)
  (ask node +S-TrieNode-key+ key))
(define (trie-node-value! node value)
  (ask node +S-TrieNode-value+ value))
(define (trie-node-suffix! node suffix)
  (ask node +S-TrieNode-suffix+ suffix))
(define (trie-node-next! node next)
  (ask node +S-TrieNode-next+ next))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Make TrieLevelContainer class
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (MAKE-TrieLevel self container level find-f add-f remove-f)
  (lambda (message)
    (cond
      ((= message +G-TrieLevel-container+)
       (lambda () container))
      ((= message +G-TrieLevel-level+)
       (lambda () level))
      ((= message +G-TrieLevel-find-function+)
       (lambda () find-f))
      ((= message +G-TrieLevel-add-function+)
       (lambda () add-f))
      ((= message +G-TrieLevel-remove-function+)
       (lambda () remove-f))

      ((= message +S-TrieLevel-container+)
       (lambda (NEW-container) (set! container NEW-container)))
      ((= message +S-TrieLevel-level+)
       (lambda (NEW-level) (set! level NEW-level)))

      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; TODO: equals
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Object-equals+)
       (lambda (other)
         '()))

      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; TODO: hash code
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Object-hash-code+)
       (lambda ()
         '()))
      
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; TODO: to string
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Object-to-string+)
       (lambda ()
         '()))
      
      (else +nil+))))

(define (CREATE-TrieLevel container level find-f add-f remove-f)
  (create-instance MAKE-TrieLevel container level find-f add-f remove-f))

(define (trie-level-container c)
  (ask c +G-TrieLevel-container+))
(define (trie-level-level c)
  (ask c +G-TrieLevel-level+))
(define (trie-level-find-function c)
  (ask c +G-TrieLevel-find-function+))
(define (trie-level-add-function c)
  (ask c +G-TrieLevel-add-function+))
(define (trie-level-remove-function c)
  (ask c +G-TrieLevel-remove-function+))

(define (trie-level-container! c container)
  (ask c +S-TrieLevel-container+ container))
(define (trie-level-level! c level)
  (ask c +S-TrieLevel-level+ level))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Make Trie class
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (MAKE-Trie self root level-find-f level-add-f level-remove-f equal-p)
  (define (add-trie-node! node suffix data)
    (let* ((trie-node-next (trie-node-next node))
           (next-level (if (null? trie-node-next) (CREATE-TrieLevel '() 0 level-find-f level-add-f level-remove-f) trie-node-next))
           (trie-node (CREATE-TrieNode (car suffix) data (cdr suffix) '())))
      (level-add-f next-level trie-node)
      (trie-node-next! node next-level)
      (trie-node-suffix! node '())
      (trie-node-value! node '())
      trie-node))
  (define (recur-extend-trie! node node-suffix suffix data)
    (let ((node-suffix-car (car node-suffix))
          (node-suffix-cdr (cdr node-suffix))
          (suffix-car (car suffix))
          (suffix-cdr (cdr suffix)))
      (if (equal-p node-suffix-car suffix-car)
          (let* ((data-in-trie (trie-node-value node))
                 (next-node (add-trie-node! node node-suffix-cdr data-in-trie)))
            (recur-extend-trie! next-node node-suffix-cdr suffix-cdr data))
          (let ((data-in-trie (trie-node-value node)))
            (add-trie-node! node node-suffix-cdr data-in-trie)
            (add-trie-node! node suffix-cdr data)))))
  (define (recur-find node suffix)
    (if (and (null? (trie-node-suffix node))
             (equal? (trie-node-key node) (car suffix)))
        (recur-find (level-find-f (trie-node-next node) (cadr suffix)) (cdr suffix))
        (cons node suffix)))
  (define (trie-add! node key-lst node-data)
    (let* ((to-extend (recur-find node key-lst))
           (node-to-extend (car to-extend))
           (suffix-to-extend (cdr to-extend)))
      (recur-extend-trie! node-to-extend (trie-node-suffix node-to-extend) suffix-to-extend node-data)))
  
  (lambda (message)
    (cond
      ((= message +M-Trie-add+)
       (lambda (key-lst data)
         (trie-add! root key-lst data)))
      
      ((= message +M-Trie-find+)
       (lambda (key-lst)
         (trie-node-value (car (recur-find root key-lst)))))

      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; TODO: equals
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Object-equals+)
       (lambda (other)
         '()))

      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; TODO: hash code
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Object-hash-code+)
       (lambda ()
         '()))
      
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; TODO: to string
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Object-to-string+)
       (lambda ()
         '()))

      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; type
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Object-type+)
       (lambda () 'Trie))
      
      (else +nil+))))

(define (CREATE-Trie root level-find-f level-add-f level-remove-f equal-p)
  (create-instance MAKE-Trie root level-find-f level-add-f level-remove-f equal-p))

(define (trie-add! trie node-lst data)
  (ask trie +M-Trie-add+ node-lst data))

(define (trie-find trie node-lst)
  (ask trie +M-Trie-find+ node-lst))

